//
// Created by Administrator on 2022/10/24.
//

#include <iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

void printArr(int *arrP, int n)
{
    for (int i = 0; i < n; ++i)
        printf("%d ", *arrP++);
    printf("\n");
}

void randomArr(int *arrP,int n)
{
    srand((int)time(0));
    for(int i=0;i<n;i++)
        arrP[i]=rand();
}

bool checkSort(int *arr,int n)
{
    for(int i=0;i<n-1;i++){
        if (arr[i]>arr[i+1])
            return false;
    }
    return true;
}


int main()
{

    int len = 100;
//    int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int arr[len];
    randomArr(arr,len);
//    printArr(arr, len);
    int step = len / 2;
    while (step > 0)
    {
        for (int i = step; i < len; i += step)
        {
            int j = i;
            int var = arr[j + step];
            while (j >= 0 && var < arr[j])
            {
                arr[j+step] = arr[j];
                j-=step;
            }
            arr[j+step]=var;
        }
        step/=2;
    }
    cout<<checkSort(arr,len)<<endl;
    printArr(arr,len);
}

